#include <stdio.h>
//返回val的索引，不存在返回-1
int find_pos1(int a[], int n, int val) {
    int s=0, e=n-1;
    int mid;
    while(s<=e) {
        mid = (s+e)/2;
        if(val > a[mid]) {
            s = mid+1;
        }else if(val == a[mid]) {
            return mid;
        }else {
            e = mid-1;
        }
    }
    return -1;
}


//返回第一个比val大的元素的索引
int find_pos2(int a[], int n, int val) {
    int s=0, e=n-1;
    int mid;
    while(s<=e) {
        mid = (s+e)/2;
        if(val >= a[mid]) {
            s = mid+1;
        }else {
            e = mid-1;
        }
    }
    return s;
       /*****
       *s=0: 所有值都比val大
       *s=n: 所有值都不大于val
       *****/
}

int main(void)
{
    int a[] = {1, 2, 3, 3, 4, 4, 5, 6};
    int i;
    for(i=0; i<8; i++) {
        printf("%d ", a[i]);
    }
    putchar('\n');
    for(i=0; i<8; i++) {
        printf("idx of %d in a: %d\n", a[i], find_pos1(a, 8, a[i]));
    }
    printf("idx of %d in a: %d\n", i, find_pos1(a, 8, i));
    for(i=0; i<8; i++) {
        printf("idx of first more then %d in a: %d\n", i, find_pos2(a, 8, i));
    }
    return 0;
    
}
